﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace text.dfs
{
    /// <summary>
    /// 学习动态规划的入门程序
    /// </summary>
    public class df
    {
        #region 斐波那契数列
        /// <summary>
        /// 斐波那契数列-1基础解法 
        /// 时间复杂度：指数n
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int fib(int n)
        {
            if (n == 1 || n == 2) return 1;
            return fib(n - 1) + fib(n - 2);
        }
        /// <summary>
        /// 斐波那契数列-2递归加记录重复计算的数组
        /// 时间复杂度： n
        /// 空间复杂度： n
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int fibtwo(int n)
        {

            int[] memo = new int[n + 1];
            return helper(memo, n);
        }
        public static int helper(int[] memo, int n)
        {
            if (n == 0 || n == 1) return n;
            if (memo[n] != 0) return memo[n];
            memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
            return memo[n];
        }
        /// <summary>
        /// 斐波那契数列-3 备忘录独立写法
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int fibthree(int n)
        {
            if (n == 0) return 0;
            int[] dp = new int[n + 1];
            //base case
            dp[0] = 0; dp[1] = 1;
            //状态转移
            for (int i = 2; i < n; i++)
            {
                dp[n] = dp[n - 1] + dp[n - 2];
            }
            return dp[n];
        }
        /// <summary>
        /// 斐波那契数列-4 状态转移方程
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int fibfour(int n)
        {
            if (n == 0 || n == 1) return n;
            int prev = 1, curr = 1;
            for (int i = 3; i < n; i++)
            {
                int sum = prev + curr;
                prev = curr;
                curr = sum;
            }
            return curr;
        }
        #endregion
        #region 凑零钱问题
        /// <summary>
        /// 暴力递归
        /// </summary>
        /// <param name="coin">可以的硬币种类</param>
        /// <param name="amount">凑出的硬币数值</param>
        /// <returns></returns>
        public static int coinChange(int[] coins, int amount)
        {
            if (amount == 0) return 0;
            if (amount < 0) return -1;
            int res = int.MaxValue;
            foreach (var coin in coins)
            {
                int number = coinChange(coins, amount - coin);
                if (number == -1) continue;
                res = Math.Min(res, number);
            }
            return res;
        }
        /// <summary>
        /// 带有备忘录的递归
        /// 自上而下
        /// </summary>
        /// <param name="coins"></param>
        /// <param name="amount"></param>
        /// <returns></returns>
        public static int coinChangetwo(int[] coins, int amount)
        {
            int[] memo = new int[coins.Length + 1];
            memo = memo.Select(x => x = -666).ToArray();
            return dp(memo, coins, amount);
        }
        public static int dp(int[] memo, int[] coins, int amount)
        {
            if (amount == 0) return 0;
            if (amount < 0) return -1;
            int res = int.MaxValue;
            if (memo[amount] != -666)
                return memo[amount];
            foreach (var coin in coins)
            {
                int number = coinChange(coins, amount - coin);

                if (number == -1) continue;
                res = Math.Min(res, number + 1);
            }
            memo[amount] = (res == int.MaxValue) ? -1 : res;
            return memo[amount];
        }
        /// <summary>
        /// 带有备忘录的递归
        /// 自下而上
        /// 为啥 dp 数组初始化为 amount + 1 呢，
        /// 因为凑成 amount 金额的硬币数最多只可能等于 amount（全用 1 元面值的硬币），
        /// 所以初始化为 amount + 1 就相当于初始化为正无穷，便于后续取最小值
        /// </summary>
        /// <param name="coins"></param>
        /// <param name="amount"></param>
        /// <returns></returns>
        public static int coinChangethree(int[] coins, int amount)
        {
            int[] dp = new int[coins.Length + 1];
            dp = dp.Select(x => x = amount + 1).ToArray();
            dp[0] = 0;
            for (int i = 0; i < amount; i++)
            {
                foreach (var coin in coins)
                {
                    if (i - coin < 0)
                        continue;
                    dp[i] = Math.Min(dp[i], dp[i - coin] + 1);
                }
            }
            return (dp[amount] == amount + 1) ? -1 : dp[amount];
        }
        #endregion
    }
}